package 牛客剑指专题二刷.链表;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 链表中环的入口节点
 * 法1：重复节点问题，哈希表
 * 法2：从起点出发，快指针路程是慢指针2被，可以证明相遇点到入口 = 头结点到入口;通过快慢指针找到焦点，然后根据相等算出入口
 */
public class JZ23 {
    class ListNode{
        int val;
        ListNode next = null;
        ListNode(int val){
            this.val = val;
        }
    }


    public ListNode EntryNodeOfLoop(ListNode pHead) {
        Set<ListNode> set = new HashSet<>();
        ListNode t = pHead;
        while(t != null){
            if(set.contains(t)){
                return t;
            }
            set.add(t);
            t = t.next;
        }
        return t;
    }



    public ListNode getMeetNode(ListNode head){
        ListNode slow = head, fast =head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) return slow;
        }
        return null;
    }
    public ListNode EntryNodeOfLoop2(ListNode pHead) {
        ListNode meetNode = getMeetNode(pHead);
        if(meetNode == null) return null;
        ListNode start = pHead;
        while(start != meetNode){
            start = start.next;
            meetNode = meetNode.next;
        }
        return meetNode;
    }
}
